package com.study.lu.动态规划;

public class 打家劫舍 {
    /**
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * <p>
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/house-robber
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 1};
        int n = rob(nums);
        n = rob2(nums);
        System.out.println(n);

    }

    private static int rob2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int n_2 = nums[0];
        int n_1 = Math.max(nums[0], nums[1]);
        int n = 0;
        for (int i = 2; i < nums.length; i++) {
            n = Math.max(n_1, n_2 + nums[i]);
            n_2 = n_1;
            n_1 = n;
        }
        return n_1;
    }

    /**
     * @param nums
     * @return
     */
    private static int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        //
        int[] dps = new int[nums.length];
        dps[0] = nums[0];
        dps[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dps[i] = Math.max(dps[i - 1], dps[i - 2] + nums[i]);
        }

        return dps[nums.length - 1];

    }
}
